#include <stdio.h>
#include <stdlib.h>
#include "grafo.h"

/*
Função que armazena as ruas do sistema num grafo
Entrada:-n_streets: 	numero total de ruas da cidade
        -vertc:		    matriz com o grafo
*/
int get_streets(int n_streets, float** graph){
	int i = 0;
	int vertA, vertB;
	float weight;

	for( i = 0; i < n_streets; i++){
		scanf("%d %d %f", &vertA, &vertB, &weight);
        graph_insert(graph, vertA-1, vertB-1, weight);
	}

	return 0;
}

/*
Analisa a matriz e retorna a maior distancia para o melhor vertice
*/
int find_best_vertex_distance(float **mat, int n_corners){
    float best_value=100000000;
    float aux;
    int i,j;

    for(i=0;i<n_corners;i++){
        aux=0;
        // verifica a linha
        for(j=0;j<n_corners;j++){
            if(mat[i][j]>aux){      // Pega o maior valor
                aux=mat[i][j];
            }
        }
        if(aux<best_value){
            best_value=aux;
        }
    }
    return best_value;
}


int main(){
	int n_streets;	// Numero total de ruas do sistema
    int n_corners;  // Numero total de esquinas
    float **graph, **best_distances;

	scanf("%d %d", &n_corners, &n_streets);

    // Aloca espaço do grafo
    graph=graph_init(n_corners);

    // Leitura dos valores das ruas
	get_streets(n_streets, graph);

    best_distances=graph_FloydWarshall(graph, n_corners);

    // encontra a maxima distancia para o melhor lugar para o hospital
    printf("%d\n",find_best_vertex_distance(best_distances,n_corners));

	return 0;
}
